#pragma once

#include <array>
#include <string>
#include <vector>

namespace solution_076
{

class Solution
{
public:
    std::string minWindow(std::string s, std::string t)
    {
        if (s.empty() || t.empty())
            return "";

        int num_required_ch = 0;
        std::array<int, 128> t_num_ch{0};
        for (auto ch : t) {
            if (t_num_ch.at(ch) == 0)
                ++num_required_ch;
            ++t_num_ch.at(ch);
        }

        std::vector<int> ids;
        for (int i = 0; i < (int)s.size(); ++i) {
            if ( t_num_ch.at( s.at(i) ) )
                ids.push_back(i);
        }

        int substr_l = 0;
        int substr_r = s.size();

        int win_l = 0;
        int win_r = 0;

        std::array<int, 128> win_num_ch{0};
        while (win_r < (int)ids.size()) {
            auto ch_r = s.at(ids.at(win_r));
            auto num_ch_r = ++win_num_ch.at(ch_r);
            if (num_ch_r == t_num_ch.at(ch_r))
                --num_required_ch;

            while (num_required_ch == 0 && win_l <= win_r) {
                if (ids.at(win_r) - ids.at(win_l) < substr_r - substr_l) {
                    substr_l = ids.at(win_l);
                    substr_r = ids.at(win_r);
                }

                auto ch_l = s.at(ids.at(win_l));
                auto num_ch_l = --win_num_ch.at(ch_l);
                if (num_ch_l < t_num_ch.at(ch_l))
                    ++num_required_ch;

                ++win_l;
            }

            ++win_r;
        }

        if (substr_r < (int)s.size())
            return s.substr(substr_l, substr_r - substr_l + 1);
        else
            return "";
    }
};

}  /* namespace solution_076 */
